\documentclass[prodmode]{acmsmall}
\usepackage{amsmath,amssymb}
\acmVolume{X}
\acmNumber{X}
\acmArticle{X}
\acmYear{2012}
\acmMonth{2}


%-------------------- Paper specific macros --------------------------

\def\floor#1{{\left\lfloor#1\right\rfloor}}
\def\ceil#1{{\left\lceil#1\right\rceil}}
\def\tfloor#1{{\lfloor#1\rfloor}}
\def\tceil#1{{\lceil#1\rceil}}

\def\union{\cup}
\def\cut{\cap}
\def\eps{\varepsilon}

\newcommand{\reals}{\mathrm{I\!R}}
\newcommand{\nats}{\mathrm{I\!N}}

\def\cost{\mathrm{cost}}
\def\l{\chi}
\def\r{\chi'}

\def\med{\mathop{\mathrm{med}}}
\def\I{\mathcal{I}}
\def\Ithr{\mathcal{I}_3}
\def\IthrS{\mathcal{I}_3^-}
\def\IthrL{\mathcal{I}_3^+}
\def\sep{\!\!:\!\!}

\newtheorem{claim}[theorem]{Claim}
\newtheorem{mechanism}[theorem]{Mechanism}

\def\insertfig#1#2#3{%
\begin{figure}[t]
%\centerline{\includegraphics[angle=-90,width=#1]{#2}}
\centerline{\includegraphics[width=#1]{#2}}
\caption{#3}
%\vspace*{-2mm}
\end{figure}}



%-------------------- Paper specific macros --------------------------

\begin{document}
\markboth{D.~Fotakis and C.~Tzamos}{On the Power of Deterministic Mechanisms for Facility Location Games}

\title{On the Power of Deterministic Mechanisms for Facility Location Games}
\author{DIMITRIS FOTAKIS
\affil{National Technical University of Athens}
CHRISTOS TZAMOS
\affil{Massachusetts Institute of Technology}}

\begin{abstract}
We investigate the approximability of $K$-Facility Location by deterministic strategyproof mechanisms.
%
Our main result is an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with at least 5 agents, any such mechanism either admits a unique dictator, or always places the facilities at the two extremes.
%
Thus, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for 2-Facility Location on the line is precisely $n-2$, where $n$ is the number of agents. Another rather surprising consequence is that the {\sc Two-Extremes} mechanism of \cite{PT09} is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for 2-Facility Location on the line.
%
The proof of the characterization employs several new ideas and technical tools, which provide new insights into the behavior of deterministic mechanisms for multiple Facility Location games, and may be of independent interest.
%
Employing one of these tools, we show that for every $K \geq 3$, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for $K$-Facility Location, even for simple instances with $K+1$ agents.
%
%Our results nicely complement known deterministic strategyproof mechanisms, and explain how (and to which extend) one can allocate multiple facilities on the real line in a way both efficient and incentive compatible.
\end{abstract}


\category{F.2.2}{Theory of Computation}{Analysis of Algorithms and Problem Complexity}
\category{J.4}{Computer Applications}{Social and Behavioral Sciences}[Economics]

\terms{Algorithms; Theory; Economics}

\keywords{Algorithmic Mechanism Design; Social Choice; Facility Location Games}

\acmformat{Fotakis, D., and Tzamos, C. 2012. On the Power of Deterministic Mechanisms for Facility Location Games.}

\begin{bottomstuff}
This work was partially supported by an NTUA Basic Research Grant (PEBE 2009).

Authors' addresses: D.~Fotakis, Division of Computer Science, School of Electrical and Computer Engineering, National Technical University of Athens, 15780 Athens, Greece, {\tt fotakis@cs.ntua.gr}\,.
%
C.~Tzamos, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, {\tt tzamos@mit.edu}\,.
\end{bottomstuff}

\maketitle


\input{intro}
\input{prelim}
\input{2facilities}
\input{3agents}
\input{Nagents}
\input{3facilities}


\section{Discussion and Open Problems}

An open problem is whether one can use the techniques in the proof of Theorem~\ref{thm:3agents}, and extend the impossibility result of Theorem~\ref{thm:3facilities} to non-anonymous mechanisms.

Two other intriguing directions for further research have to do with the approximability of $K$-Facility Location, for $K \geq 4$, by randomized and deterministic imposing mechanisms. For $3$-Facility Location on the line, there are both a randomized and a deterministic imposing mechanism with approximation ratio $n-1$.
%
%Furthermore, for all $K \geq 3$, {\sc Inversely Proportional} is strategyproof and achieves an approximation ratio of $(K+1)/2$ for instances with $K+1$ agents.
%
Therefore, it is very interesting to obtain a deterministic imposing (resp. randomized) mechanism with a bounded approximation ratio for $K$-Facility Location, for all $K \geq 4$ (resp. and all $n \geq K+2)$, or to show that no such mechanism exists.
%
Moreover, we are aware of a deterministic imposing mechanism for $2$-Facility Location on the line that escapes the characterization of Theorem~\ref{thm:2fac-gen}, albeit with an approximation ratio of $n-1$. However, this raises the question about the best approximation ratio achievable by deterministic imposing mechanisms for 2-Facility and 3-Facility Location on the line.

\bibliographystyle{acmsmall}
\bibliography{mechdesign}

\newpage\appendix
\input{app-moves}
\input{app-3agents}
\input{app-Nagents}
\input{app-3facilities}
\end{document}



We believe that one can use the techniques developed in the proof of Theorem~\ref{thm:3agents}, and exclude the possibility of a nice mechanism for $K$-Facility Location on the line, for all $K \geq 3$. The proof should begin with the equivalent of Lemma~\ref{l:i-separated}, but now has to consider a few additional cases, which further complicates the technical arguments.
%
%Similarly, we believe that one can extend the techniques developed in the proof of Theorem~\ref{thm:3agents} to more general metric spaces, such as tree metrics, and exclude the possibility of a nice mechanism for $2$-Facility Location in metric spaces more general than the line.

Two interesting directions for further research have to do with understanding the power and the limitations of randomized and (deterministic) imposing mechanisms for $K$-Facility Location, with $K \geq 4$.
%
As for randomized mechanisms,
%we know that a combination of {\sc Two-Extremes} and {\sc Proportional} gives a stategyproof $(n-1)$-approximation mechanism for $3$-Facility Location on the line \cite{LSWZ10}. Moreover, for every $K \geq 4$, {\sc Inversely Proportional} is strategyproof and achieves an approximation ratio of $(K+1)/2$ for instances with $K+1$ agents \cite{EGTPS11}, which are among the hardest ones for  deterministic anonymous mechanisms (Theorem~\ref{thm:3facilities}).
%
it would be very interesting if one could either prove or disprove the existence of a strategyproof mechanism with a bounded approximation ratio for Facility Location with $K \geq 4$ facilities and $n \geq K+2$ agents. In fact, it would be even more interesting if one could obtain a characterization of a randomized strategyproof mechanisms with a bounded approximation ratio for $K$-Facility Location, even for the line.

Deterministic imposing mechanisms require that the agents should connect to the nearest facility to their \emph{reported} location, and thus, are more powerful than their non-imposing counterparts. To this end, we observe that there are imposing strategyproof mechanisms that escape Theorem~\ref{thm:2fac-gen} and Theorem~\ref{thm:3facilities}.
%
For instance, an imposing variant of {\sc Dictatorial}, with the first facility placed at $\med\vec{x}$, instead of $x_j$, is strategyproof, $(n-1)$-approximate, and neither admits a dictator, not allocates the facilities to the two extremes.
%
Moreover, there is an imposing strategyproof mechanism that achieves an approximation ratio of $n-1$ for $3$-Facility Location on the line. For every instance $\vec{x}$, this mechanism allocates two facilities to the two extremes, and lets $d_l$ (resp. $d_r$) be the distance of the leftmost (resp. rightmost) agent to the furthest agent on the left (resp. right) of $m = (\min\vec{x}+\max\vec{x})/2$. Then, the third facility is placed at
%
$\min\{m,  \min\vec{x} + \max\{d_l, 2 d_r\}\}$, if $d_l \geq d_r$, and at
%
$\max\{m, \max\vec{x} - \min\{2 d_l, d_r\}\}$, otherwise.
%
Hence, an interesting direction for research has to do with a better understanding of the power of deterministic imposing mechanisms. As a first step, it would be interesting to know whether deterministic imposing mechanisms can achieve an approximation ratio better that $n-2$ (resp. $n-1$) for $2$-Facility (resp. $3$-Facility) Location on the line, and any bounded approximation ratio for $K$-Facility Location with $K \geq 4$.
